lib/Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/geometria/is_convex_polygon.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textit{\textcolor{Brown}{/*}} \\
   6 \mbox{}\textit{\textcolor{Brown}{\ \ Returns\ positive\ if\ a-b-c\ make\ a\ left\ turn.}} \\
   7 \mbox{}\textit{\textcolor{Brown}{\ \ Returns\ negative\ if\ a-b-c\ make\ a\ right\ turn.}} \\
   8 \mbox{}\textit{\textcolor{Brown}{\ \ Returns\ 0.0\ if\ a-b-c\ are\ colineal.}} \\
   9 \mbox{}\textit{\textcolor{Brown}{\ */}} \\
  10 \mbox{}\textcolor{ForestGreen}{double}\ \textbf{\textcolor{Black}{turn}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}a\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}b\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ point\ \textcolor{BrickRed}{\&}c\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  11 \mbox{}\ \ \textcolor{ForestGreen}{double}\ z\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{(}b\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{-}\ a\textcolor{BrickRed}{.}x\textcolor{BrickRed}{)*(}c\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{-}\ a\textcolor{BrickRed}{.}y\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{-}\ \textcolor{BrickRed}{(}b\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{-}\ a\textcolor{BrickRed}{.}y\textcolor{BrickRed}{)*(}c\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{-}\ a\textcolor{BrickRed}{.}x\textcolor{BrickRed}{);} \\
  12 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{fabs}}\textcolor{BrickRed}{(}z\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$}\ \textcolor{Purple}{1e-9}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0.0}\textcolor{BrickRed}{;} \\
  13 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ z\textcolor{BrickRed}{;} \\
  14 \mbox{}\textcolor{Red}{\}} \\
  15 \mbox{} \\
  16 \mbox{}\textit{\textcolor{Brown}{/*}} \\
  17 \mbox{}\textit{\textcolor{Brown}{\ \ Returns\ true\ if\ polygon\ p\ is\ convex.}} \\
  18 \mbox{}\textit{\textcolor{Brown}{\ \ False\ if\ it's\ concave\ or\ it\ can't\ be\ determined}} \\
  19 \mbox{}\textit{\textcolor{Brown}{\ \ (For\ example,\ if\ all\ points\ are\ colineal\ we\ can't\ }} \\
  20 \mbox{}\textit{\textcolor{Brown}{\ \ make\ a\ choice).}} \\
  21 \mbox{}\textit{\textcolor{Brown}{\ */}} \\
  22 \mbox{}\textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Black}{isConvexPolygon}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ vector\textcolor{BrickRed}{$<$}point\textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{\&}p\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  23 \mbox{}\ \ \textcolor{ForestGreen}{int}\ mask\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  24 \mbox{}\ \ \textcolor{ForestGreen}{int}\ n\ \textcolor{BrickRed}{=}\ p\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();} \\
  25 \mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  26 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ j\textcolor{BrickRed}{=(}i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{)\%}n\textcolor{BrickRed}{;} \\
  27 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ k\textcolor{BrickRed}{=(}i\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{)\%}n\textcolor{BrickRed}{;} \\
  28 \mbox{}\ \ \ \ \textcolor{ForestGreen}{double}\ z\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{turn}}\textcolor{BrickRed}{(}p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{],}\ p\textcolor{BrickRed}{[}j\textcolor{BrickRed}{],}\ p\textcolor{BrickRed}{[}k\textcolor{BrickRed}{]);} \\
  29 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}z\ \textcolor{BrickRed}{$<$}\ \textcolor{Purple}{0.0}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  30 \mbox{}\ \ \ \ \ \ mask\ \textcolor{BrickRed}{$|$=}\ \textcolor{Purple}{1}\textcolor{BrickRed}{;} \\
  31 \mbox{}\ \ \ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}z\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{0.0}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  32 \mbox{}\ \ \ \ \ \ mask\ \textcolor{BrickRed}{$|$=}\ \textcolor{Purple}{2}\textcolor{BrickRed}{;} \\
  33 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  34 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}mask\ \textcolor{BrickRed}{==}\ \textcolor{Purple}{3}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{;} \\
  35 \mbox{}\ \ \textcolor{Red}{\}} \\
  36 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ mask\ \textcolor{BrickRed}{!=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  37 \mbox{}\textcolor{Red}{\}} \\
  38
  39 } \normalfont\normalsize